package cn.corffen.test.algorithm.leetcode.easy;

import java.util.Locale;

public class Question67 {

    public static void main(String[] args) {
        String a = "1010";
        String b = "1011";
        System.out.println(String.format(Locale.CHINA, "a+b = %s", new Question67().addBinary(a, b)));
    }

    public String addBinaryFrom(String a, String b) {
        return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
    }

    /**
     * 逐位计算,逢二进一
     *
     * @param a
     * @param b
     * @return
     */
    public String addBinary(String a, String b) {
        int n = a.length(), m = b.length();
        if (n < m) return addBinary(b, a);
        int L = Math.max(n, m);

        StringBuilder sb = new StringBuilder();
        int carry = 0, j = m - 1;
        for (int i = L - 1; i > -1; --i) {
            if (a.charAt(i) == '1') ++carry;
            if (j > -1 && b.charAt(j--) == '1') ++carry;

            if (carry % 2 == 1) sb.append('1');
            else sb.append('0');

            carry /= 2;
        }
        if (carry == 1) sb.append('1');
        sb.reverse();

        return sb.toString();
    }

    public String addBinaryO(String a, String b) {
        int base = 2;
        int n = a.length(), m = b.length();
        if (n < m) return addBinary(b, a);
        int L = Math.max(n, m);

        char[] buff = new char[n + 1];
        StringBuilder sb = new StringBuilder();
        int carry = 0;

        for (int i = n - 1, j = m - 1; i >= 0; i--) {
            if (j >= 0) {
                carry += (a.charAt(j) - '0');
                j--;
            }
            carry += (b.charAt(i) - '0');
            buff[i + 1] = (char) (carry % base + '0');
            carry /= base;
        }
        if (carry == 0) new String(buff);
        sb.reverse();

        return sb.toString();
    }

}
